package com.practice.graph;


/**
 * N people, each pair can be friend, enemy or no relationship. 
 * Both friend and enemy relationship are transitive. 
 * - A friend's friend is also friend,
 * - A friend's enemy is enemy, 
 * - An enemy's friend is enemy.
 * - Any two enemies are friends
 * 
 * Input:
 * a, b, relationship defines relationship between a[] and b[].
 * i, j are two people
 * 
 * Output:
 * what's relationship between i and j?
 * 
 * 1: friend, 0: enemy, -1: no relationship
 * 
 */
public class FriendEnemy {
	private int[] color;
	
	public void buildRelationGraph(int N, int[] a, int[] b, int[] relation) throws Exception {
		color = new int[N];
		int[][] g = new int[N][N];
		
		for (int i=0; i<a.length; i++) {
			if (relation[i] == 0) {		// enemy
				g[a[i]][b[i]] = -1;
				g[b[i]][a[i]] = -1;
			}
			else {						// friend
				g[a[i]][b[i]] = 1;
				g[b[i]][a[i]] = 1;
			}
		}
		
		int c = 1;
		for (int i=0; i<N; i++) {
			if (color[i] == 0) {
				dfs(N, g, i, c);
				c += 2;
			}
		}
	}
	
	private void dfs(int N, int[][] g, int i, int c) throws Exception {
		if (color[i] > 0) {
			if (color[i] != c) throw new Exception("Relation graph has contradiction!");
			return;
		}
		
		color[i] = c;
		for (int j=0; j<N; j++) {
			if (g[i][j] == 1) {
				dfs(N, g, j, c);
			}
			else if (g[i][j] == -1) {
				int nextC = ((c+1)/2)*4 - 1 - c;
				dfs(N, g, j, nextC);
			}
		}
	}
	
	/**
	 * 1: friend
	 * 0: enemy
	 * -1: no relationship
	 */
	public int getRelation(int i, int j) {
		if (color[i] == color[j]) return 1;
		if (color[i]/2 == color[j]/2) return 0;
		return -1;
	}
}
